package org.basis.algorithm.tree.practice;

import org.basis.algorithm.tree.common.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 最低公共祖先
 *
 * @author Mr_wenpan@163.com 2021/12/22 14:35
 */
public class LowestCommonAncestor2 {

    public static void main(String[] args) {

    }

    public static TreeNode<Integer> find(TreeNode<Integer> head, TreeNode<Integer> node1, TreeNode<Integer> node2) {
        if (head == null || node1 == null || node2 == null) {
            return null;
        }
        // 先序遍历先找出每个节点的父节点关系，并记录在hash表
        HashMap<TreeNode<Integer>, TreeNode<Integer>> map = new HashMap<>();
        HashSet<TreeNode<Integer>> set = new HashSet<>();
        map.put(head, null);
        getParentMap(head, map);
        // 逮住一个节点往上走，直到走到头节点
        TreeNode<Integer> cur = node1;
        while (cur != null) {
            set.add(cur);
            // 往父节点走
            cur = map.get(cur);
        }

        while (node2 != null) {
            if (set.contains(node2)) {
                return node2;
            }
            node2 = map.get(node2);
        }

        // 无公共祖先
        return null;
    }

    public static void getParentMap(TreeNode<Integer> head, HashMap<TreeNode<Integer>, TreeNode<Integer>> map) {
        if (head == null) {
            return;
        }
        // 维护父子关系
        if (head.left != null) {
            map.put(head.left, head);
        }
        if (head.right != null) {
            map.put(head.right, head);
        }
        getParentMap(head.left, map);
        getParentMap(head.right, map);
    }

    /**
     * 宽度优先遍历维护父子关系
     */
    public static void getParentMap2(TreeNode<Integer> head, HashMap<TreeNode<Integer>, TreeNode<Integer>> map) {
        if (head == null) {
            return;
        }
        // 维护父子关系
        LinkedList<TreeNode<Integer>> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            TreeNode<Integer> poll = queue.poll();
            TreeNode<Integer> left = poll.left;
            TreeNode<Integer> right = poll.right;
            if (left != null) {
                queue.add(left);
                map.put(poll.left, poll);
            }
            if (right != null) {
                queue.add(right);
                map.put(poll.right, poll);
            }
        }
    }

    /**
     * 中序遍历构建父子关系
     */
    public static void getParentMap3(TreeNode<Integer> head, HashMap<TreeNode<Integer>, TreeNode<Integer>> map) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        while (!stack.isEmpty() || head != null) {
            if (head == null) {
                // 弹出一个节点
                TreeNode<Integer> pop = stack.pop();
                if (pop.left != null) {
                    map.put(pop.left, pop);
                }
                if (pop.right != null) {
                    map.put(pop.right, pop);
                }
                head = pop.right;
                continue;
            }
            stack.push(head);
            head = head.left;
        }
    }

    /**
     * 先序遍历构建父子关系
     */
    public static void getParentMap4(TreeNode<Integer> head, HashMap<TreeNode<Integer>, TreeNode<Integer>> map) {
        if (head == null) {
            return;
        }
        Stack<TreeNode<Integer>> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode<Integer> pop = stack.pop();
            if (pop.left != null) {
                map.put(pop.left, pop);
            }
            if (pop.right != null) {
                map.put(pop.right, pop);
            }
            // 先压右再压左
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

}
